
"""
102. 二叉树的层序遍历
"""
import collections
from asyncio import Queue
from typing import Optional, List

from com.siyuan.TreeNode import TreeNode


class Solution:

    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        """
        广度优先遍历
        相当于一层层依次遍历，利用队列作为辅助
        """
        # 用于存储每一层数据
        res = []

        if not root:
            return res

        # 辅助队列(永远只存储一层节点)
        q = collections.deque()
        q.append(root)

        # 两个遍历，第一个遍历层数，第二个遍历每层的各个元素
        while q:
            # 控制节点数，保证每次while循环只取出一层
            size = len(q)

            # 记录每一层
            level = []

            for i in range(0, size):
                # 取出队列第一个元素
                cur = q.popleft()
                level.append(cur.val)
                # 将当前节点的左右子节点存储到队列中，用于遍历下一层
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            res.append(level)

        return res

sl = Solution()
print(sl.levelOrder(TreeNode(1)))